//
//  GETree.h
//  GETestRender
//
//  Created by Louis CHU on 13/09/11.
//  Copyright 2011 Dung's Lab. All rights reserved.
//


#ifndef GE_TREE_H
#define GE_TREE_H

namespace game_engine {
	namespace core {
        
//****************************************************************************************
#pragma mark - 
#pragma mark CTNode
        template<class T>
		class CTNode {
            
        protected:
        CTNode<T>*          _parent;
			CTNode<T>*          _left;
			CTNode<T>*          _right;
			T                   _element;
        int                 _size;
            
        public:
			CTNode(const T& element):_element(element),_left(0),_right(0),_parent(0),_size(1){};
            
            virtual ~CTNode(){}
            //-------------------------------------------------------------------------
			//METHODS
        public:
            //----------------------------
            bool isLeaf()
            {
                return !_left && !_right;
            }
            
            //-------------------------------------------------------------------------
			//PROPRIETIES
        public:
            CTNode<T>*  parent() { return _parent; }
            void        parent ( CTNode<T> * node ) { _parent = node; }
            //----------------------------
            CTNode<T>*  left() { return _left; }
            void        left ( CTNode<T>* node ) 
            { 
                if ( !node && _left ) _size -- ;
                if ( node && !_left ) _size ++ ;
                _left = node;
            }
            //----------------------------
            CTNode<T>*  right() { return _right; }
            void        right ( CTNode<T>* node ) 
            { 
                if ( !node && _right ) _size -- ;
                if ( node && !_right ) _size ++ ;
                _right = node; 
            }
            //----------------------------
            T           element() { return _element; }
            void        element ( T e ) { _element = e; }
        };     

//****************************************************************************************
#pragma mark - 
#pragma mark CBinarySearchTNode
        template<class T>
        class CBinarySearchTNode
        {
        public:
            CBinarySearchTNode(const T& element): CTNode(element){}
            virtual ~ CBinarySearchTNode(){}
        //-------------------------------------------------------------------------
			//METHODS
        protected:
            //------------------------------------------------
            void insertNode(CBinarySearchTNode<T> * root, CBinarySearchTNode<T> * newNode)
            {
                //CBinarySearchTNode<T> * newNode = new CBinarySearchTNode<T>(element);
                if (root->isLeaf()) 
                {
                    if (newNode->element() < root->element())   root->left(newNode);
                    else                                        root->right(newNode);
                    
                }
                else if (newNode->element() < root->element()) 
                {
                    this->insertNode(root->left(), newNode);
                }
                else
                {
                    this->insertNode(root->right(), newNode);
                }
            }
        };
//****************************************************************************************
#pragma mark - 
#pragma mark CBalancedBinarySearchTNode
        

        template<class T>
        class CBalancedBinarySearchTNode
        {
        private:
            const static int kBalancedValue         = 0; 
            const static int kBalancedLeftValue     = -1; 
            const static int kBalancedRightValue    = 1; 
            const static int kUnbalancedLeftValue   = -2; 
            const static int kUnbalancedRightValue  = 2; 
            
            CBalancedBinarySearchTNode<T> *         _maxLeft;
            CBalancedBinarySearchTNode<T> *         _minRight;

        public:
            CBalancedBinarySearchTNode( const T& element): CBinarySearchTNode(element), _maxLeft(0), _minRight(0){}
            virtual ~ CBalancedBinarySearchTNode(){}
            
        //-------------------------------------------------------------------------
			//METHODS
        private:
            
            int unbalancingValue() { return size(_right) - size(_left); }
            
            void balancy()
            {
                int unbalancingValue = this->unbalancingValue();
                if (unbalancingValue < kUnbalancedLeftValue 
                    || unbalancingValue > kUnbalancedRightValue)
                {
                    //this case is not valid
                    return;
                }
                
                if (unbalancingValue >= kBalancedLeftValue 
                    && unbalancingValue <= kBalancedRightValue )
                {
                    //this tree is balanced
                    return;
                }
                
                if (unbalancingValue == kUnbalancedLeftValue) 
                {
                    
                }
                else
                {
                    
                }
                
                
            }
            
                        
            //Pre-cond: unbalancingValue == kUnbalancedRightValue
            // => the size of right branch >= 2 and _minRight is not NULL
            void balancyToLeft()
            {
                
            }
        //-------------------------------------------------------------------------
        //PUBLIC
        
        //-------------------------------------------------------------------------
			//PRIORITIES
        public:
            CBalancedBinarySearchTNode<T> * maxLeft(){ return _maxLeft; }
            void maxLeft( CBalancedBinarySearchTNode<T> * node) { _maxLeft = node; }
            
            CBalancedBinarySearchTNode<T> * minRight(){ return _minRight; }
            void minRight( CBalancedBinarySearchTNode<T> * ndoe) { _minRight = node; }
        };
        //****************************************************************************************
#pragma mark - 
#pragma mark inline for CBalancedBinarySearchTNode

        //Pre-cond: unbalancingValue == kUnbalancedLeftValue
        // => the size of left branch >= 2 and _maxLeft is not NULL
        inline void balancyToRight(CBalancedBinarySearchTNode<T> * root)
        {
            CBalancedBinarySearchTNode<T> * maxLeftTemp = root->maxLeft();
            if (!_maxLeft->isLeaf()) //or  _maxLeft have only left branch ,not right branch
            {
                if(root->maxLeft() == root->left()) //or the left of _maxLeft's parent is _maxLeft
                {
                    root->left(_maxLeft->left());
                    root->maxLeft(root->maxLeft()->maxLeft());
                }
                else //or the right of _maxLeft's parent is _maxLeft
                {
                    root->maxLeft()->parent()->right(root->maxLeft()->left());
                    root->maxLeft(root->maxLeft()->left());
                }
            }
            else
            {
                if(root->maxLeft() == root->left())                
                {
                    root->left(0);
                    root->maxLeft(0);
                }
                else
                {
                    root->maxLeft()->parent()->right(0);
                    root->maxLeft(_maxLeft->parent());
                }
            }
            switchNode(maxLeftTemp, root);
            
            if (root->minRight()) {
                maxLeftTemp->parent(root->minRight());
                root->left(maxLeftTemp);
            }
            else
            {
                maxLeftTemp->parent(root);
                root->right(maxLeftTemp);
            }
            
            root->minRight(maxLeftTemp);
           
            maxLeftTemp->left(0);
            //maxLeftTemp->right(0);
            maxLeftTemp->maxLeft(0);
            
            root->left()->balancy();
            root->right()->balancy();
        }

        
//****************************************************************************************
#pragma mark - 
#pragma mark General
        
        //----------------------------
        inline size (CTNode<T> node)
        {
            if(node) return node->size();
            else     return 0;
        }
        //----------------------------
        inline CTNode<T> * leftRotate( CTNode<T> * root )
        {
            CTNode<T> * right = root->right();
            if ( !right ) return root;
            CTNode<T> * leftOfRight = right->left();
            root->right( leftOfRight );
            right->left( root );
            return right;
        }
        //----------------------------
        inline CTNode<T> * rightRotate( CTNode<T> * root )
        {
            CTNode<T> * left = root->left();
            if ( !left ) return root;
            CTNode<T> * rightOfLeft = left->right();
            root->left( rightOfLeft );
            left->right( root );
            return left;
        }
        //----------------------------
        inline void switchNode(CTNode<T> * node1, CTNode<T> * node2)
        {
            T e = node1->element();
            node1->element(node2->element());
            node2->element(e);
        }
    }
}

#endif